二叉树的前中后序遍历：递归法+迭代法

2023-08-11 01:55| 来源: 网络整理| 查看: 265

文章目录前言一、二叉树的代码二、递归法1.二叉树的前、中、后序的递归遍历三、迭代法1.前序遍历2.后序遍历2.中序遍历扩展：判断单值二叉树

前言

本文总结自LeetCode的题库，其中代码参考题解，题解中还有许多其他的方法，本文代码以简洁易理解为基本要求。这里也不对二叉树的基本知识进行讲解，只对实现的代码进行解释介绍

力扣题库： * 二叉树深度优先遍历 * 前序遍历： 0144.二叉树的前序遍历 * 后序遍历： 0145.二叉树的后序遍历 * 中序遍历： 0094.二叉树的中序遍历

提示：以下代码不理解时，只需要自己画图推算一下，就能理解

一、二叉树的代码

二叉树节点的最简单结构

class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } 二、递归法

1.二叉树的前、中、后序的递归遍历

实现输入二叉树，返回遍历的数组：只是 list.add(root.val)的位置变化，代码其实一样。

public static List preOrder(TreeNode root, ArrayList list) { if(root==null){ return list; }else{ //前序遍历，最先加入父节点 list.add(root.val); if(root.left!=null){ preOrder(root.left,list); } //中序遍历的 add() 位置，为中间输出 if(root.right!=null){ preOrder(root.right,list); } //后续遍历的 add() 位置，为最后输出 } return list; }

三、迭代法

1.前序遍历

提示：迭代法实现二叉树的前序遍历

//2.迭代法 //要保持遍历的深度，所以需要用到一个stack来维持 //注意栈是先进后出，所以需要先把右子节点入栈 public static List preOrder2(TreeNode root) { List list = new ArrayList(); Stack stack = new Stack(); if(root == null){ return list; } stack.push(root); while(!stack.isEmpty()){ TreeNode node = stack.pop(); list.add(node.val); if(node.right!=null){ stack.push(node.right); } if(node.left!= null){ stack.push(node.left); } } return list; }

2.后序遍历

提示：后序遍历的迭代代码与前序遍历其实一样，相当于顺序翻转一下，只是子节点的push()顺序需要变化一下

public List postorderTraversal(TreeNode root) { List list = new ArrayList(); Stack stack = new Stack(); if(root == null){ return list; } stack.push(root); while(!stack.isEmpty()){ TreeNode node = stack.pop(); list.add(node.val); if(node.left!= null){ stack.push(node.left); } if(node.right!=null){ stack.push(node.right); } } //这句反转的代码参考自leetCode官方，只是反转的操作会使效率降低 Collections.reverse(list); return list; }

2.中序遍历

差别比较大的是中序遍历的迭代法，依旧使用栈来维护深度

分析

1.我们必须实现一直深度的入左子节点2.中间节点在我们入左子节点的时候就相当于已经入栈3.从左子节点（中间节点）如何跳到右子节点，所以这里需要增加一个临时节点p，用于保存当前的节点 public List inorderTraversal(TreeNode2 root) { List res = new ArrayList(); Stack stack = new Stack(); //用临时节点p来保存中间节点信息 TreeNode2 p = root; while(!stack.isEmpty() || p!=null){ //当前节点如果不为空，那么一直入栈，并且指向自己的左节点，实现中间节点和左子节点的入栈操作 while(p != null){ stack.push(p); p = p.left; } //左子节点入栈完毕，开始出站。第一个出栈的就是最底层的那一个左子节点，入list p = stack.pop(); res.add(p.val); /** 1. 如果当前节点没有右子节点（叶子结点就没有），那么此时p=null 2. 如果当前节点不是叶子节点，实现了对右子节点的跳转输出 3. 所以此时的循环条件是，p非空说明没有遍历完，栈为空则说明出栈完毕，可以结束遍历 */ p = p.right; } return res; } 扩展：判断单值二叉树遍历二叉树，判断如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。 // 分析;当时我是直接在非空里面进行if else，进行中序遍历 // 出现的问题是：[2,2,2,5,9],[9,9,5,9,9]两种示例情况 // 如果 return isUnivalTree(root.left) 左子节点遍历到最后没有错误节点，接直接返回，没有判断右子树 // 如果 isUnivalTree(root.left)，然后在最后直接return true，或出左子树判断到错误，依旧往下执行，返回true的情况 public static boolean isUnivalTree(TreeNode2 root) { if (root == null) { return true; } else { int val = root.val; if (root.left != null && root.left.val != val) { return false; } if (root.right != null && root.right.val != val) { return false; } //这行代码非常强！ return isUnivalTree(root.left) && isUnivalTree(root.right); } }

【本文地址】

公司简介

联系我们